package cn.zzf.algs.note.exercise.fundamental;

import edu.princeton.cs.algs4.StdOut;
import org.junit.jupiter.api.Test;

import java.util.Collections;
import java.util.stream.IntStream;

/**
 * @author GaoFeng
 * @date 2019/11/22 20:47
 */
public class Ex1_1_22 {

    /**
     * 递归实现二分搜索，并跟踪栈调用
     *
     * */

    @SuppressWarnings( "unchecked")
    private <T extends Comparable> int binarySearch(T[] array, T element, int begin, int end, int step) {

        printStep(step, begin, end);

        if (begin > end) {
            return -1;
        }

        int mid = (begin + end) / 2;

        if (element.compareTo(array[mid]) < 0) {
            // find left
            return binarySearch(array, element, begin, mid - 1, step + 1);
        } else if (element.compareTo(array[mid]) > 0) {
            // find right
            return binarySearch(array, element, mid + 1, end, step + 1);
        } else {
            return mid;
        }

    }

    private void printStep(int step, int begin, int end) {
        String stepStr = String.join("", Collections.nCopies(step, " "))
                + "begin -> " + begin + " end -> " + end;
        StdOut.println(stepStr) ;
    }

    @Test
    public void test() {
        int size = 100;
        Integer[] nums = IntStream.rangeClosed(1, size).sequential().boxed().toArray(Integer[]::new);
        int index = this.binarySearch(nums, 101, 0, nums.length - 1, 0);
        StdOut.println(index);
    }


}
